#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		char a[100];
		int ans=0,k=0,tem;
		scanf("%s",a);
		int len=strlen(a);
		while(a[k]!='\0')
		{
			ans+=(a[k]-'0')*(int)pow(9.0,(double)(len-1-k));
			//printf("ans%d\n",ans);
			k++;
		}
		int fans[100];
		k=0;
		while(ans!=0)
		{
			fans[k]=ans%2;
			ans/=2;
			k++;
		}
		for(int i=k-1;i>=0;i--)
		{
			printf("%d",fans[i]);
		}
		printf("\n");
	}
}
